package main

import "fmt"

func main() {
	ans := numIslands([][]int{{1, 1, 1, 1, 0},
		{1, 1, 0, 1, 0},
		{1, 1, 0, 0, 0},
		{0, 0, 0, 0, 0},
	})
	fmt.Printf("ans: %v\n", ans)
}

var direction = []position{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

type position struct {
	x, y int
}

func numIslands(grid [][]byte) int {
	m, n := len(grid), len(grid[0])
	visit := make(map[int]map[int]bool, m)
	for i := 0; i < len(grid); i++ {
		visit[i] = make(map[int]bool, n)
	}
	queue := []position{}
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' && !visit[i][j] {
				queue = append(queue, position{i, j})
				visit[i][j] = true
				ans++
			}
			for len(queue) != 0 {
				cur := queue[0]
				queue = queue[1:]
				for _, d := range direction {
					nextP := position{cur.x + d.x, cur.y + d.y}
					if nextP.x >= 0 && nextP.x < m &&
						nextP.y >= 0 && nextP.y < n &&
						grid[nextP.x][nextP.x] == 1 &&
						!visit[nextP.x][nextP.y] {
						queue = append(queue, nextP)
						visit[nextP.x][nextP.y] = true
					}

				}
			}
		}
	}
	return ans
}
